import java.util.*;
import java.util.stream.Collectors;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/1 5:37 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class Solution {


    int[] getSelfCheckingNodes(List<Node> nodes, int[] keyNodes, int faultSrc) {

        Map<Integer, int[]> map = new HashMap<>();

        Map<Integer, List<Integer>> mapBefore = new HashMap<>();

        for (Node node : nodes) {

            int[] nextNodes = node.nextNodes;

            map.put(node.id, nextNodes);

            for (int nextNode : nextNodes) {

                List<Integer> beforeNodes = mapBefore.getOrDefault(nextNode, new ArrayList<>());

                beforeNodes.add(node.id);

                mapBefore.put(nextNode, beforeNodes);

            }

        }



        Set<Integer> notifiylist = getNotifiylist(faultSrc, map);

        Set<Integer> checkList = getCheckList(faultSrc, mapBefore, keyNodes, notifiylist);

        List<Integer> temp = checkList.stream().sorted().collect(Collectors.toList());

        int[] result = new int[checkList.size()];

        for (int i = 0; i < checkList.size(); i++) {

            result[i] = temp.get(i);

        }

        return result;

    }



    private Set<Integer> getCheckList(int faultSrc, Map<Integer, List<Integer>> mapBefore, int[] keyNodes,

                                      Set<Integer> notifiylist) {

        Set<Integer> keyList = Arrays.stream(keyNodes).boxed().collect(Collectors.toSet());

        Set<Integer> checkList = new HashSet<>();

        checkList.add(faultSrc);

        for (Integer nodeId : notifiylist) {

            if (keyList.contains(nodeId)) {

                check(mapBefore, checkList, nodeId);

            }

        }

        return checkList;

    }



    private void check(Map<Integer, List<Integer>> mapBefore, Set<Integer> checkList, Integer nodeId) {

        checkList.add(nodeId);

        List<Integer> beforeNodes = mapBefore.getOrDefault(nodeId, new ArrayList<>());

        Deque<Integer> beforeNodesStack = new ArrayDeque<>(beforeNodes);

        while (!beforeNodesStack.isEmpty()) {

            Integer beforeNode = beforeNodesStack.poll();

            if (checkList.add(beforeNode)) {

                beforeNodesStack.addAll(mapBefore.getOrDefault(beforeNode, new ArrayList<>()));

            }

        }

    }



    private Set<Integer> getNotifiylist(int faultSrc, Map<Integer, int[]> map) {

        Deque<Integer> stack = new ArrayDeque<>();

        stack.offer(faultSrc);

        Set<Integer> notifiylist = new HashSet<>();

        while (!stack.isEmpty()) {

            Integer nextNode = stack.poll();

            if (notifiylist.add(nextNode)) {

                int[] nextNodes = map.get(nextNode);

                for (int id : nextNodes) {

                    stack.offer(id);

                }

            }

        }

        return notifiylist;

    }



    void process(List<Node> nodes, int[] keyNodes, int faultSrc) {

        var result = this.getSelfCheckingNodes(nodes, keyNodes, faultSrc);

        System.out.print(Arrays.stream(result).

                mapToObj(String::valueOf).collect(Collectors.joining(" ")));

    }
}
